#define _CRT_SECURE_NO_WARNINGS  1


class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> v;
        int key = 0;

        while (key < nums.size() - 1)
        {
            if (nums[key] > 0)
            {
                key++;
            }
            int left = key + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] + nums[key] > 0)
                {
                    right--;
                }
                else if (nums[left] + nums[right] + nums[key] < 0)
                {
                    left++;
                }
                else
                {
                    //if(nums[left] != nums[left-1] && nums[right] != nums[right+1])
                    v.push_back({ nums[key],nums[left],nums[right] });
                    right--;
                    left++;
                    while (right > left && nums[right] == nums[right + 1])
                    {
                        right--;
                    }
                    while (right > left && nums[left] == nums[left - 1])
                    {
                        left++;
                    }
                }
            }
            key++;
            while (key < nums.size() && nums[key] == nums[key - 1])
            {
                key++;
            }
        }
        return v;
    }
};